package com.example.demo.leetcode;

public class _24_两两交换链表中的节点 {

    public static void main(String[] args) {
        ListNode node = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
        ListNode node1 = swapPairs(node);
        System.out.println(node1.val);
    }

    /**
     * 方法一：递归
     * 时间复杂度：O(n）
     * 空间复杂度：O(1)
     *
     * @param head
     * @return {@link ListNode}
     * @author WangYX
     * @date 2024/03/07 16:29
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode node = new ListNode(-1, head);
        swap(node);
        return node.next;
    }

    public static void swap(ListNode pre) {
        if (pre == null) {
            return;
        }
        ListNode head = pre.next;
        if (head == null) {
            return;
        }
        ListNode tail = pre.next.next;
        if (tail == null) {
            return;
        }
        ListNode suffix = pre.next.next.next;
        pre.next = tail;
        tail.next = head;
        head.next = suffix;
        swap(head);
    }


}
